The present invention relates to a method and apparatus for measuring and controlling the load carried by a telecommunications system for transactional applications, and a system incorporating the same.
Packet switched networks achieve very high speed by keeping the amount of interpretation of each packet at nodes in the heart of the network to a minimum. In general, two decisions need to be made about the packet at each node it encounters: which output link it is to be directed to; and what treatment (e.g. prioritisation) it should be given within the node, both absolutely and relative to other packets.
In production networks using the Internet Protocol version 4 (IPv4) the decisions have until very recently been based on a very limited subset of the fields in the IP header. Typically the output decision is made solely on the basis of the destination address. Treatments within a node are restricted to two classes of prioritisation for normal data traffic and network control traffic, based on two distinct values of the Precedence field (part of the Type of Service (ToS) octet). Network control traffic, which is generated entirely by the administrative and operational mechanisms of the network rather than by users, is typically given absolute priority over all other traffic. All user traffic (the remainder) is treated identically. Normally no guarantees are offered as to the delivery of the traffic, and the service offered to users of these networks are described as xe2x80x98best effortsxe2x80x99 services.
Thus in each node (router, host workstation) which routes or forwards packets in an IPv4, each packet which arrives on an incoming or ingress interface is treated as follows:
The packet is read from the incoming interface
The destination Address field and, optionally, the Type of Service (ToS) field are extracted from the packet
The Destination Address field and, optionally, the ToS field are used as indices into a forwarding table constructed by means of the dynamic routing protocols to find the correct output link for the packet. Routing responsive to the contents of the ToS field is currently extremely uncommon although it has in principal been available since the early definition of IP.
If the node is able to provide differential treatment of packets directed to a given output, the ToS field is inspected to determine the treatment to be given. Typically differential treatment is based on the Precedence value in the ToS field, and may be limited to two distinct classes of treatment, one for network control traffic (a small but vital component) and a second for normal data traffic (the rest); the classes of traffic are directed into a set of distinct first-in, first-out (FIFO) queues associated with each output.
The packets are scheduled into the available output bandwidth from the queues according to a scheduling algorithm. Typically this is an absolute priority mechanism in which any network control packet is given absolute priority over any normal data packet: if there are any network control packets waiting when a slot is available on the output link, the packet at the head of the network control traffic queue will be output onto the link and the packet removed from the queue in preference to any waiting normal packets. Otherwise, if there is a packet waiting on the normal data traffic queue, it will be output and removed from the queue.
Some current routers include more complex mechanisms, such as additional classification, filtering, queuing, and scheduling mechanisms but there is no uniformity as to how these facilities are invoked, and they are not widely deployed in production networks.
The limited capabilities of the existing IP networks to be able to differentiate classes of traffic restrict the ability of network operators to offer services with enhanced quality of service (QoS) to their customers. By QoS we mean such things as constraints on the delay experienced by a packet, the variation in delays experienced by a packet, the relative priority for packets of a particular class, and the amount of bandwidth available to a class of packets passing through a network.
It is becoming clear that certain customers and types or application need (and customers would be prepared to pay for) a service that is an improvement over the existing best efforts service.
One of groups of the services that is likely to be most used to users of an IP data network is transactional services. Transactional services include, but are not limited to World-Wide Web accesses and Remote Procedure Call invocations including, for example, interactive database accesses. Transactional services are a major componentxe2x80x94perhaps as much as 70%xe2x80x94of today""s data traffic.
Within an IP packet switched data network all data is carried in the form of IP xe2x80x98datagramsxe2x80x99. An IP datagram is a packet consisting of an IP header and an IP payload as shown in FIG. 2.
The IP Header provides all the information needed to route the packet through the network.
IP datagrams are used to carry the information of numerous different protocols across the network (the protocol in use is indicated by a specific bit pattern in the Protocol field of the IP header). One of these protocols is the Transport Control Protocol (TCP) reliable byte stream transport protocol. In this case the IP payload is made up of a TCP header and the TCP user payload data. TCP is used as the transporting protocol for a large fraction of all user traffic carried across IP networks.
The TCP header is used to carry information which allows the receiving station to reconstruct the transmitted byte stream thereby achieving the desired reliability of delivery. Packets successfully received at the receiving end of a connection are positively acknowledged by the sending of a specific acknowledgement back to the origin of the packet.
A fundamental characteristic of TCP is its ability to adapt the rate of flow of data across a network to provide near optimal use of the available network bandwidth. TCP conforms its transmission rate to the available bandwidth by:
Increasing its transmission rate in response to successful receipt and acknowledgement of packets
Reducing its transmission rate in response to missing acknowledgements, indicating packet loss (typically due to network congestion).
In normal operation, the flow rate of a TCP flow starts at a low value and ramps up through a xe2x80x98slow start phasexe2x80x99 and a xe2x80x98congestion avoidance phasexe2x80x99 to a maximum value as the first few packets are acknowledged. At some point in this initial ramp up either all data will have been sent or a packet will be lost. If a packet is lost (indicated by missing acknowledgements) the flow rate is reduced by 50% and ramp up restarts from the reduced value.
If multiple packets are lost, the flow is reduced to a minimum and the whole process repeats after a delay designed to allow the network to recover from the congestion that caused the dropped packets. Typically transactional services open a TCP reliable byte stream connection from a client to a server and issue a xe2x80x98requestxe2x80x99 which is in the order of a few tens to a few hundreds of bytes long (i.e. one or two packets). The request is sent from the client to a server which processes it, performing some local operation and then returns some xe2x80x98responsexe2x80x99 data which may vary from a few bytes (such as a success code) to a few tens of kilobytes (such as an image for a web page) over a period of between, say, a few hundred milliseconds to 20 seconds.
One problem in integrating such transactional services into most standard QoS schemes is that the overhead of reserving resources to guarantee the delivery of the data is out of proportion to the size of the data delivered and the limited persistence of the connection. Each transaction or small set of transactions is likely to need a separate reservation especially in the web access service case.
A further problem lies in that the short duration of the flow associated with a request or response does not allow the conventional flow control algorithms of TCP to achieve steady state. This tends to mean that the flow may be categorised as xe2x80x98fragilexe2x80x99: loss of a single packet will set the TCP flow control algorithm back into slow start mode with consequential impact on the throughput of the connection. By contrast a well established flow, relies on a few dropped packets to control the bandwidth used and TCP is designed to cope with occasional dropped packets once steady state is established.
A third problem is that the inherent burstiness of human-mediated interactions (for example web accesses) makes it difficult to put in place a service which will allow the network to control or predict the load of such transactions and hence to offer predictable service for them.
Furthermore, the essentially random destinations to which web accesses are directed makes provisioning of such services difficult.
The invention seeks to provide an improved method and apparatus for packet-by-packet admission control whereby to support implementation of Differentiated Services in a packet-switched network.
According to a first aspect of the present invention there is provided a method of monitoring telecommunications network traffic comprising the steps of: receiving a packet stream comprising packets each identified as belonging to one of at least three classes; calculating a difference between the numbers of packets received identified as belonging to a first and a second of said classes; and deriving a measure of traffic load on the network responsive to said difference.
Preferably the method also comprises the steps of: providing statistical distribution data descriptive of said traffic load; deriving said measure of traffic load on the network responsive to said statistical distribution data.
In a preferred embodiment said first class is indicative of the beginning of a transactional burst, and said second class is indicative of the end of a transactional burst.
Preferably each initial packet of a transactional burst is identified as belonging to said first class and each final packet of a transactional burst is identified as belonging to said second class.
In a preferred embodiment wherein a transactional burst comprises a single packet, said packet is marked as belonging both to said first and to said second classes.
Preferably an indication of which class a packet belongs to is contained in the header of said packet.
In a preferred embodiment said packet is of an Internet protocol.
In one preferred embodiment, said packet is of an Internet Protocol version 4 having a header and said indication is located within a second octet of said header.
In a second preferred embodiment said packet is of an Internet Protocol version 6 having a header and said indication is located within the bits 4-7 of a first octet and bits 0-3 of a second octet of said header.
In one preferred embodiment wherein said header comprises a DSCP field, said indications are encoded using four values of said DSCP field.
According to a second aspect of the present invention there is provided a method of performing packet data network admission control comprising the steps of: receiving a packet stream comprising packets each identified as belonging to one of at least three classes; calculating a difference between the numbers of packets received identified as belonging to a first and a second of said classes; deriving a measure of traffic load on the network responsive to said difference; and accepting and rejecting packets responsive to said measure.
In a preferred embodiment, the method of performing packet data network admission control comprises the steps of: receiving a packet on a given traffic flow; if said packet is of a first class indicative of the start of a new traffic burst then, if a previously stored measure of current traffic load is indicative of an admission rejection condition being satisfied in respect of said received packet discard said packet, otherwise increment said measure and forward said packet; if said packet is of a second class not indicative of the start or end of a traffic burst then forward said packet; and if said packet is of a third class indicative of the end of a traffic burst then decrement said measure of current traffic load and forward said packet.
Preferably, said measure of current load is a difference between the number of packets of said first class previously forwarded and the number of packets of said third class previously forwarded.
Preferably, an indication of which class a packet belongs to is contained in the header of said packet.
Preferably, said packet is of an Internet protocol.
In a first preferred embodiment, said packet is of an Internet Protocol version 4 having a header and said indication is located within a second octet of said header.
In a second preferred embodiment, said packet is of an Internet Protocol version 6 having a header and said indication is located within the bits 4-7 of a first octet and bits 0-3 of a second octet of said header.
In one preferred embodiment wherein said header comprises a DSCP field, said indications are encoded using four values of said DSCP field.
According to a third aspect of the present invention there is provided a method of preventing abuse of the admission control method comprising the steps of: receiving a traffic flow comprising data packets; monitoring the rate of occurrence of packets indicative of starts and ends of transactional bursts within said traffic flow; if said rate meets a suspected-abuse criterion, a first packet received on said traffic flow is marked as indicative of the start of a transaction and a second packet received on said traffic flow is marked as indicative of the end of a transaction; if said packet is marked as indicative of the start of a new transaction then, if a previously stored measure of current traffic load is indicative of an admission rejection condition being satisfied in respect of said received packet discard said packet, otherwise increment said measure and forward said packet; if said packet is marked as not indicative of the start or end of a traffic burst then forward said packet; and if said packet is marked as indicative of the end of a transaction then decrement said measure of current traffic load and forward said packet.
According to a fourth aspect of the present invention there is provided a method of transmitting traffic load information within a packet data stream comprising transactional bursts, comprising the steps of: labelling each initial packet of transactional bursts as belonging to a first class; labelling each final packet of transactional bursts as belonging to a second class; labelling each other packet of transactional bursts as belonging to one or more further distinct classes whereby to identify starts and ends of such transactional bursts within a packet data stream.
According to a fifth aspect of the present invention there is provided a packet network node comprising: an input arranged to receive a packet stream comprising packets each identified as belonging to one of at least three classes; a processor arranged to calculate a difference between the numbers of packets received identified as belonging to a first and a second of said classes and to calculate a measure of traffic load on the network responsive to said difference.
According to a sixth aspect of the present invention there is provided a packet network node comprising: an input arranged to receive a packet traffic flow; a processor arranged to determine for each packet received on said traffic flow, (a) whether said packet is of a first class indicative of the start of a new traffic burst and if so, to determine whether a previously stored measure of current traffic load is indicative of an admission rejection condition being satisfied in respect of said received packet and if so to discard said packet and otherwise to increment said measure and forward said packet, (b) whether said packet is of a second class not indicative of the start or end of a traffic burst and if so to forward said packet, and (c) whether said packet is of a third class indicative of the end of a traffic burst and if to decrement said measure of current traffic load and forward said packet.
According to a seventh aspect of the present invention there is provided a packet network node for preventing abuse of admission control comprising: an input arranged to receive a packet traffic comprising data packets; a processor arranged to monitor the rate of occurrence of packets indicative of starts and ends of transactional bursts within said traffic flow; if said rate meets a suspected-abuse criterion, to mark a first packet received on said traffic flow as indicative of the start of a transaction and to mark a second packet received on said traffic flow as indicative of the end of a transaction; if said packet is marked as indicative of the start of a new transaction then, if a previously stored measure of current traffic load is indicative of an admission rejection condition being satisfied in respect of said received packet to discard said packet, otherwise to increment said measure and forward said packet; if said packet is marked as not indicative of the start or end of a traffic burst then to forward said packet; and if said packet is marked as indicative of the end of a transaction then to decrement said measure of current traffic load and to forward said packet.
According to an eighth aspect of the present invention there is provided a communications system comprising apparatus according to any one of the foregoing aspects of the present invention.
The invention also provides for a system for the purposes of digital signal processing which comprises one or more instances of apparatus embodying the present invention, together with other additional apparatus.
According to a ninth aspect of the present invention there is provided a program for a computer on a machine-readable medium embodying a method according to any one of the foregoing aspects of the present invention.
The preferred features may be combined as appropriate, as would be apparent to a skilled person, and may be combined with any of the aspects of the invention.